#include <iostream>
#include <BinaryTree.hpp>

using namespace std;

class Solution
{
    const int minRange = -40000;
    const int maxRange = 40000;

public:
    int maxSumBST(TreeNode *root)
    {
        int ans = 0;
        auto [success, maxSum, minEV, maxEV] = dfs(root, ans);
        return max(ans, 0);
    }

    // isbt,maxV,ElementRange<,>
    std::tuple<bool, int, int, int> dfs(TreeNode *root, int &ans)
    {
        int maxleft = 0, maxright = 0;
        int minEV = root->val, maxEV = root->val;
        bool success = true;
        if (root->left == nullptr && root->right == nullptr)
        {
            ans = max(ans, root->val);
            return {true, root->val, root->val, root->val};
        }
        if (root->left != nullptr)
        {
            auto [s, maxSum, minE, maxE] = dfs(root->left, ans);
            maxleft = maxSum;
            minEV = min(minEV, minE);
            maxEV = max(maxEV, maxE);
            if (!(s && root->val > maxE))
                success = false;
        }
        if (root->right != nullptr)
        {
            auto [s, maxSum, minE, maxE] = dfs(root->right, ans);
            maxright = maxSum;
            minEV = min(minEV, minE);
            maxEV = max(maxEV, maxE);
            if (!(s && root->val < minE))
                success = false;
        }
        if (success)
            ans = max(ans, maxleft + maxright + root->val);
        return {success, success ? (root->val + maxleft + maxright) : max(maxleft, maxright), minEV, maxEV};
    }
};

int main()
{
    cout << "Code1373" << endl;
    Solution s;
    TreeNode *tree = CreatTree("[4,8,null,6,1,9,null,-5,4,null,null,null,-3,null,10]", "null");
    cout << s.maxSumBST(tree) << endl;
    return 0;
}